#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    //@ ysh's method
    // bool is_palindrome(string &s)
    // {
    //     int i = 0;
    //     int j = s.size() - 1;
    //     for (; i <= j; i++, j--)
    //     {
    //         if (s[i] != s[j])
    //         {
    //             return false;
    //         }
    //     }
    //     return true;
    // }
    // void traceback(string &s)
    // {
    //     bool flag = true;
    //     for (auto s : path)
    //     {
    //         if (!is_palindrome(s))
    //         {
    //             flag = false;
    //             break;
    //         }   // bool is_palindrome(string &s)
    // {
    //     int i = 0;
    //     int j = s.size() - 1;
    //     for (; i <= j; i++, j--)
    //     {
    //         if (s[i] != s[j])
    //         {
    //             return false;
    //         }
    //     }
    //     return true;
    // }
    // void traceback(string &s)
    // {
    //     bool flag = true;
    //     for (auto s : path)
    //     {
    //         if (!is_palindrome(s))
    //         {
    //             flag = false;
    //             break;
    //         }
    //     }
    //     if (flag)
    //     {
    //         res.push_back(path);
    //     }
    //     string last_str = path.back();
    //     if (last_str.size() == 1)
    //     {
    //         return;
    //     }
    //     for (size_t i = 1; i < last_str.size(); i++)
    //     {
    //         string s1(last_str.begin(), last_str.begin() + i);
    //         string s2(last_str.begin() + i, last_str.end());
    //         path.pop_back();
    //         path.push_back(s1);
    //         path.push_back(s2);
    //         traceback(s);
    //         path.pop_back();
    //         path.pop_back();
    //         path.push_back(last_str);
    //     }
    // }
    // vector<vector<string>> partition(string s)
    // {
    //     res.clear();
    //     path.clear();
    //     path.push_back(s);
    //     traceback(s);
    //     return res;
    // }
    // vector<vector<string>> res;
    // vector<string> path;
    //     }
    //     if (flag)
    //     {
    //         res.push_back(path);
    //     }
    //     string last_str = path.back();
    //     if (last_str.size() == 1)
    //     {
    //         return;
    //     }
    //     for (size_t i = 1; i < last_str.size(); i++)
    //     {
    //         string s1(last_str.begin(), last_str.begin() + i);
    //         string s2(last_str.begin() + i, last_str.end());
    //         path.pop_back();
    //         path.push_back(s1);
    //         path.push_back(s2);
    //         traceback(s);
    //         path.pop_back();
    //         path.pop_back();
    //         path.push_back(last_str);
    //     }
    // }
    // vector<vector<string>> partition(string s)
    // {
    //     res.clear();
    //     path.clear();
    //     path.push_back(s);
    //     traceback(s);
    //     return res;
    // }
    // vector<vector<string>> res;
    // vector<string> path;

    //@ book answer
    // bool is_palindrome(string &s, int start, int end)
    // {
    //     for (int i = start, j = end; i < j; i++, j--)
    //     {
    //         if (s[i] != s[j])
    //         {
    //             return false;
    //         }
    //     }
    //     return true;
    // }
    // void traceback(string &s, int start_index)
    // {
    //     if (start_index >= (int)s.size())
    //     {
    //         res.push_back(path);
    //         return;
    //     }
    //     for (int i = start_index; i < (int)s.size(); i++)
    //     {
    //         if (is_palindrome(s, start_index, i))
    //         {
    //             string str = s.substr(start_index, i - start_index + 1);
    //             path.push_back(str);
    //         }
    //         else
    //         {
    //             continue;
    //         }
    //         traceback(s, i + 1);
    //         path.pop_back();
    //     }
    // }
    // vector<vector<string>> partition(string s)
    // {
    //     res.clear();
    //     path.clear();
    //     traceback(s, 0);
    //     return res;
    // }
    // vector<vector<string>> res;
    // vector<string> path;

    // book answer with dynamic_planning
    void cal_palindrome_map(string &s)
    {
        palindrome_map.resize(s.size(), vector<bool>(s.size(), false));
        for (int i = (int)s.size() - 1; i >= 0; i--)
        {
            for (int j = i; j < (int)s.size(); j++)
            {
                if (i == j)
                {
                    palindrome_map[i][j] = true;
                }
                else if (j - i == 1)
                {
                    palindrome_map[i][j] = (s[i] == s[j]);
                }
                else
                {
                    palindrome_map[i][j] = ((s[i] == s[j]) && palindrome_map[i + 1][j - 1]);
                }
            }
        }
    }
    void traceback(string &s, int start_index)
    {
        if (start_index >= (int)s.size())
        {
            res.push_back(path);
            return;
        }
        for (int i = start_index; i < (int)s.size(); i++)
        {
            if (palindrome_map[start_index][i])
            {
                string str = s.substr(start_index, i - start_index + 1);
                path.push_back(str);
            }
            else
            {
                continue;
            }
            traceback(s, i + 1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s)
    {
        res.clear();
        path.clear();
        cal_palindrome_map(s);
        traceback(s, 0);
        return res;
    }
    vector<vector<string>> res;
    vector<string> path;
    vector<vector<bool>> palindrome_map;
};

int main()
{
    Solution sol;
    string str = "bbb";
    vector<vector<string>> res = sol.partition(str);
    for (auto vec : res)
    {
        for (auto s : vec)
        {
            cout << s << " ";
        }
        cout << endl;
    }
    return 0;
}